#include<cstdio>
#include<cstring>
const int maxint=100000000;
int g[1101][1101],p[1101],n=0;
bool prim[9999];
void FilterPrime(int t)
{
	memset(prim,1,sizeof(prim));
	prim[0]=prim[1]=0;
	for(int i=2;i<=t;i++)
		if(prim[i])
		{
			if(i>1000)p[++n]=i;
			for(int j=i;j<=t;j+=i)
				prim[j]=0;
		}
}
bool judge(int i,int j)
{
	int t=0;
	if(i%10==j%10)t++;
	i/=10;j/=10;
	if(i%10==j%10)t++;
	i/=10;j/=10;
	if(i%10==j%10)t++;
	i/=10;j/=10;
	if(i==j)t++;
	if(t==3)return true;
	return false;
}
void MakeGraph()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(judge(p[i],p[j]))g[i][j]=1;
			else g[i][j]=maxint;
}
int dijkstra(int u,int v)
{
	int dis[1101];
	bool s[1101];
	for(int i=1;i<=n;i++)
	{
		if(i!=u)s[i]=0;
		else s[i]=1;
		dis[i]=g[i][u];
	}
	for(int k=1;k<=n-2;k++)
	{
		int w=maxint;int m=u;
		for(int i=1;i<=n;i++)
		   if(!s[i]&&dis[i]<w){m=i;w=dis[i];}
		if(m!=u)s[m]=1;
		else return maxint;
		//if(m==v)return ;
		//else return dis[v];
		for(int i=1;i<=n;i++)
			if(!s[i]&&dis[m]+g[m][i]<dis[i])
				dis[i]=dis[m]+g[m][i];
	}
	return dis[v];
}
int find(int x)
{
	for(int i=1;i<=n;i++)
		if(p[i]==x)return i;
}
void init()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==b){printf("0\n");continue;}
		int u=find(a);
		int v=find(b);
		int ans=dijkstra(u,v);
		if(ans>=maxint)printf("Impossible\n");
		else printf("%d\n",ans);
	}
}
int main()
{
	FilterPrime(9999);
	MakeGraph();
	init();
	return 0;
}


